package com.company.modeldesign;

import java.util.LinkedList;

public class FrontMiddleBackQueue {
    /**
     * FrontMiddleBack()初始化队列。
     * void pushFront(int val) 将val添加到队列的 最前面。
     * void pushMiddle(int val) 将val添加到队列的 正中间。
     * void pushBack(int val)将val添加到队里的 最后面。
     * int popFront()将 最前面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1。
     * int popMiddle() 将 正中间的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1。
     * int popBack() 将 最后面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1。
     */

    public static class QueueEntry{
        int v;
        QueueEntry preEntry;
        QueueEntry nextEntry;

        public QueueEntry(int v) {
            this.v = v;
        }
    }
    private int size;
    private QueueEntry head;
    private QueueEntry tail;
    private QueueEntry middle;
    public FrontMiddleBackQueue() {
        size = 0;
    }

    public void pushFront(int val) {
        QueueEntry queueEntry = new QueueEntry(val);
        if (head == null) {
            head = queueEntry;
            middle = head;
            tail = head;
        }else {
            queueEntry.nextEntry = head;
            head.preEntry = queueEntry;
            head = queueEntry;
        }
        size++;
    }

    public void pushMiddle(int val) {
        QueueEntry queueEntry = new QueueEntry(val);
        QueueEntry preEntry = middle.preEntry;
        QueueEntry nextEntry = middle.nextEntry;

        preEntry.nextEntry = queueEntry;
        queueEntry.nextEntry = middle;
        queueEntry.preEntry = preEntry;
        middle.preEntry = queueEntry;

        middle = queueEntry;
        size++;
    }
    public int popMiddle() {
        if (middle == null) {
            return -1;
        }
        QueueEntry preEntry = middle.preEntry;
        QueueEntry nextEntry = middle.nextEntry;

        preEntry.nextEntry = nextEntry;
        nextEntry.preEntry = preEntry;

        middle.preEntry = null;
        middle.nextEntry = null;
        size--;
        return middle.v;

    }

    public void pushBack(int val) {
        QueueEntry queueEntry = new QueueEntry(val);
        if (head == null) {
            head = queueEntry;
            middle = head;
            tail = head;
        }else {
            queueEntry.nextEntry = head;
            head.preEntry = queueEntry;
            head = queueEntry;
        }
        size++;
    }

    public int popFront() {
        if (head == null) {
            return -1;
        }
        QueueEntry entry = head;
        head = head.nextEntry;
        head.preEntry = null;
        size--;
        return entry.v;
    }



    public int popBack() {
        if (tail == null) {
            return -1;
        }
        QueueEntry entry = tail;
        tail = entry.preEntry;
        tail.nextEntry = null;
        size--;
        return entry.v;
    }
}
